package me.mingshan.leetcode;

/**
 * 61. 旋转链表
 * <p>
 * https://leetcode.cn/problems/rotate-list/description/
 * <p>
 * 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
 *
 * @author hanjuntao
 * @date 2025/8/5 0005
 */
public class L_61_rotate_list {

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        ListNode result = rotateRight(head, 5);
        ListNode.print(result);
    }

    /**
     * k=2
     * <p>
     * 1->2->3->4->5->6
     * 5->6->1->2->3->4
     * <p>
     * k=4
     * 1->2->3->4->5->6
     * 3->4->5->6->1->2
     *
     * 思路：
     *
     * 我们要找到从到倒数第k个节点，然后把该节点之后的链表从原链表分开，拼到原链表头部，返回链表头节点
     *
     * 注意：
     * k的值可能会大于链表长度，所以需要取余数
     *
     * @param head
     * @param k
     * @return
     */
    private static ListNode rotateRight(ListNode head, int k) {
        if (head == null) {
            return null;
        }

        int length = 0;
        ListNode curr = head;
        ListNode tail = null;

        while (curr != null) {
            length++;

            if (curr.next == null) {
                tail = curr;
            }

            curr = curr.next;
        }

        k = k % length;
        // 未旋转
        if (k == 0) {
            return head;
        }

        // 从index（包含）之后的链表从原链表分开，拼到原链表头部
        int index = length - k + 1;

        curr = head;
        ListNode pre = null;
        int count = 0;
        while (curr != null) {
            count++;

            if (count == index) {
                pre.next = null;
                tail.next = head;
                head = curr;
                break;
            }

            pre = curr;
            curr = curr.next;
        }

        return head;
    }
}
